package dp

import "math"

var minValue = math.MaxInt32

func coinChange(coins []int, amount int) int {
	if amount == 0 {
		return 0
	}
	// dp公式 dp[i] = min(dp[i - coins[0]],dp[i - coins[1]],...dp[i - conins[n-1)]]) + 1

	dp := make([]int, amount+1)
	dp[0] = 0
	for i := 1; i <= amount; i++ {
		dp[i] = minValue
	}

	for i := 1; i <= amount; i++ {
		for j := 0; j < len(coins); j++ {
			if coins[j] <= i {
				// 只要能找开，一定是从某些面值相加得到的，不会存在能找开但是获取不到有效值的情况
				dp[i] = min(dp[i-coins[j]]+1, dp[i])
			}
		}
	}
	if dp[amount] == minValue {
		return -1
	}
	return dp[amount]

}
